#include <string.h>
#include "gc.h"
#include "mem.h"
#include "thread.h"
#include "redexceptionobject.h"

static RedMutex mutex;
static gc_head_t container =
{
	.gc_ref		= 0,
	.gc_size	= 0,
	.gc_prev	= &container,
	.gc_next	= &container,
};

static inline int gc_list_size(gc_head_t *list)
{
	int count = 0;
	gc_head_t *gc = list->gc_next;

	while (gc != list) count++, gc = gc->gc_next;
	return count;
}

static inline void gc_list_remove(gc_head_t *node)
{
	node->gc_prev->gc_next = node->gc_next;
	node->gc_next->gc_prev = node->gc_prev;
	node->gc_prev = node;
	node->gc_next = node;
}

static inline void gc_list_append(gc_head_t *list, gc_head_t *node)
{
	node->gc_next = list;
	node->gc_prev = list->gc_prev;
	list->gc_prev->gc_next = node;
	list->gc_prev = node;
}

static void update_refs(gc_head_t *list)
{
	for (gc_head_t *gc = list->gc_next; gc != list; gc = gc->gc_next)
	{
		/* gc->ref must equals to GC_REACHABLE */
		gc->gc_ref = FROM_GC(gc)->ob_ref;
	}
}

static char _visit_unref(RedObject *self, void *args)
{
	if (!(self->ob_flags & RED_OBJECT_STATIC))
	{
		gc_head_t *gc = TO_GC(self);

		/* only cares objects with `gc->gc_ref` > 0' */
		if (gc->gc_ref > 0)
			gc->gc_ref--;
	}

	return 1;
}

static void subtract_refs(gc_head_t *list)
{
	for (gc_head_t *gc = list->gc_next; gc != list; gc = gc->gc_next)
	{
		RedObject *object = FROM_GC(gc);
		object->ob_type->tp_traverse(object, _visit_unref, NULL);
	}
}

static char move_reachable(RedObject *self, void *args)
{
	if (!(self->ob_flags & RED_OBJECT_STATIC))
	{
		gc_head_t *gc = TO_GC(self);

		if (gc->gc_ref == 0)
		{
			/* reachable but `move_unreachable` hasn't yet gotton to it */
			gc->gc_ref = 1;
		}
		else if (gc->gc_ref == GC_UNREACHABLE)
		{
			gc_list_remove(gc);
			gc_list_append((gc_head_t *)args, gc);
		}
	}

	return 1;
}

static void move_unreachable(gc_head_t *list, gc_head_t *unreachable)
{
	gc_head_t *gc = list->gc_next;

	while (gc != list)
	{
		gc_head_t *next = NULL;

		if (!gc->gc_ref)
		{
			next = gc->gc_next;
			gc->gc_ref = GC_UNREACHABLE;
			gc_list_remove(gc);
			gc_list_append(unreachable, gc);
		}
		else
		{
			RedObject *object = FROM_GC(gc);

			gc->gc_ref = GC_REACHABLE;
			object->ob_type->tp_traverse(object, move_reachable, list);
			next = gc->gc_next;
		}

		gc = next;
	}
}

static void recycle_unreachable(gc_head_t *reachable, gc_head_t *unreachable)
{
	while (unreachable->gc_next != unreachable)
	{
		gc_head_t *gc = unreachable->gc_next;
		RedObject *object = FROM_GC(gc);

		Red_REF(object);
		object->ob_type->tp_clear(object);
		Red_UNREF(object);

		if (gc == unreachable->gc_next)
		{
			RedMutex_Acquire(&mutex);
			gc->gc_ref = GC_REACHABLE;
			gc_list_remove(gc);
			gc_list_append(reachable, gc);
			RedMutex_Release(&mutex);
		}
	}
}

void Red_FreeGarbageCollector(void)
{
	RedMutex_Free(&mutex);
}

void Red_InitGarbageCollector(void)
{
	RedMutex_Init(&mutex);
}

int RedObject_GC_Collect(void)
{
	gc_head_t unreachable =
	{
		.gc_ref		= 0,
		.gc_size	= 0,
		.gc_prev	= &unreachable,
		.gc_next	= &unreachable,
	};

	/* lock GC before marking */
	RedMutex_Acquire(&mutex);

	/* mark  */
	update_refs(&container);
	subtract_refs(&container);
	move_unreachable(&container, &unreachable);

	/* unlock GC after marked */
	RedMutex_Release(&mutex);

	/* sweep */
	int count = gc_list_size(&unreachable);
	recycle_unreachable(&container, &unreachable);
	return count;
}

void RedObject_GC_Insert(RedObject *object)
{
	if (!(object->ob_flags & RED_OBJECT_STATIC))
	{
		RedMutex_Acquire(&mutex);
		gc_head_t *gc = TO_GC(object);

		/* check if already added */
		if (gc->gc_ref == GC_UNTRACK)
		{
			gc->gc_ref = GC_REACHABLE;
			gc_list_append(&container, gc);
		}

		RedMutex_Release(&mutex);
	}
}

void RedObject_GC_Remove(RedObject *object)
{
	if (!(object->ob_flags & RED_OBJECT_STATIC))
	{
		RedMutex_Acquire(&mutex);
		gc_head_t *gc = TO_GC(object);

		/* check if tracked by GC */
		if (gc->gc_ref != GC_UNTRACK)
		{
			gc->gc_ref = GC_UNTRACK;
			gc_list_remove(gc);
		}

		RedMutex_Release(&mutex);
	}
}

void RedObject_GC_Free(RedObject *object)
{
	if (!(object->ob_flags & RED_OBJECT_STATIC))
		RedMem_Free(TO_GC(object));
}

RedObject *RedObject_GC_Alloc(size_t size)
{
	gc_head_t *result = RedMem_Alloc(size + sizeof(gc_head_t));

	if (!result)
		return NULL;

	result->gc_ref = GC_UNTRACK;
	result->gc_size = size;
	result->gc_prev = result;
	result->gc_next = result;
	return FROM_GC(result);
}
